The present invention relates to orthogonal transform technique used for image processing.
Digitizing images or audio signals makes high efficiency coding technique more important. As an effective means for high efficiency coding, there is known orthogonal transform coding. Discrete Cosine Transform (DCT) in particular is suitable for high efficiency coding and is used commonly. The calculation formulas for normalized (with the same weighting given to each orthogonal coefficient) eighth order DCT are shown in the following, where X0, ..., X7 in the formulas (1) to (7) represent the sampled input values, Y0, ..., Y7 represent the orthogonally transformed output values, and Ci (i=1, ..., 7) takes a value COS (i.pi./16). EQU Y0=C4X0+C4X1+C4X2+C4X3+C4X4+C4X5 +C4X6+C4X7 (1) EQU Y1=C1X0+C3X1+C5X2+C7X3-C7X4-C5X5 -C3X6-C1X7 (2) EQU Y2=C2X0+C6X1-C6X2-C2X3-C2X4-C6X5 +C6X6+C2X7 (3) EQU Y3=C3X0-C7X1-C1X2-C5X3+C5X4+C1X5 +C7X6-C3X7 (4) EQU Y4=C4X0-C4X1-C4X2+C4X3+C4X4-C4X5 -C4X6+C4X7 (5) EQU Y5=C5X0-C1X1+C7X2+C3X3-C3X4-C7X5 +C1X6-C5X7 (6) EQU Y6=C6X0-C2X1+C2X2-C6X3-C6X4+C2X5 -C2X6+C6X7 (7) EQU Y7=C7X0-C5X1+C3X2-C1X3+C1X4-C3X5 +C5X6-C7X7 (8)
An actual apparatus realizing an eighth order DCT on the basis of the above formulas is shown in FIG. 10. X0, ..., X7 shown in FIG. 10 are eight inputs to the apparatus, and Y0, ..., Y7 are eight outputs therefrom. Each orthogonal coefficient Yi has a higher frequency component the larger the suffix number is. Ci (i=1, ...,7) is a multiplier for multiplying each sampled input by Ci. An intersection between two arrows indicates an addition of two values inputted along the two arrows. With the apparatus shown in FIG. 10, the input values X0, ..., X7 are transformed into orthogonal coefficients Y0, ..., Y7. This DCT apparatus requires as many multiplications as 64 times, thereby resulting in a large hardware scale. In view of this, a fast algorithm for reducing the number of multiplications has been presented. FIG. 11 shows an example of an eighth order Fast DCT (FDCT) apparatus. A broken line in FIG. 11 indicates an inversion of plus/minus sign. In the example shown in FIG. 11, FDCT is realized by three stages of butterfly operation (operation of calculating (a+b), (a-b) for the inputs a, b), reducing the number of multiplications to 12 times. FIG. 12 shows an example of a Fast Inverse DCT (FIDCT). The number of multiplications in this FIDCT is also reduced to 12 times. The above fast algorithm is also applicable to Discrete Sine Transform (DST).
Apart from the above description, human visual sense or acoustic sense is generally more insensitive to distortions of high frequency components than low frequency components. In high efficiency coding, therefore, it often occurs the case where a large weighting is given to the orthogonal coefficient for low frequency range, whereas a small weighting is given to the orthogona coefficient for high frequency. For this reason, multiplication for weighting each orthogonal coefficient is generally carried out after the execution of DCT. This is illustrated in FIG. 13 wherein of eight orthogonal coefficient outputs from an eighth order DCT apparatus, seven outputs are weighted by multiplying them by constants W1, ..., W7. As will be understood, weighting for N orthogonal coefficients generally requires multiplication of (N-1) times.
Further, in conventional FDCT or FDST, N (=2.sub.m)-th order orthogonal transform or inverse orthogonal transform requires multiplication as many as m.times.2.sup.m-1 times at a minimum. It is therefore necessary for real time image processing to perform considerably fast multiplication. In addition, if weighting is necessary, additional multiplications are required to thereby make it more difficult to realize an actual apparatus. For example, consider the case of two-dimensional (8.times.8) DCT for an image block composed of horizontal 8 pixels and vertical 8 pixels, 64 pixels in total. It requires multiplications 12.times.8 times in the horizontal direction and 12.times.8 times in the vertical direction, totaling 192 multiplications. If 64 pixels are weighted after two-dimensional DCT, additional 63 multiplications are required, resulting in the number of multiplications of 255 times.
In a conventional example shown in FIG. 11, in calculating one orthogonal coefficient, multiplication is serially performed m (=3) times at a maximum. If multiplication for weighting is included, the total 4 multiplications are serially performed. There arises another problem of rounding errors caused by repetitive multiplications.
As described before, human visual sense is relatively insensitive to high frequency distorsions. An orthogonal coefficient for low frequency is therefore necessary to have a higher precision than that for high frequency. However, in a conventional example of FDCT shown in FIG. 11, the final multiplication for each orthogonal coefficient has a larger multiplier the lower the frequency component for the orthogonal coefficient is. Accordingly, before the final multiplication, the higher the frequency component for the orthogonal coefficient is, it has a higher precision. In the example shown in FIG. 11, the precision of the first coefficient (Y1) relative to the seventh coefficient (Y7) before the final multiplication is: ##EQU1## Accordingly, the orthogonal coefficient for low frequency which takes an important role from the standpoint of visual sense, has larger operation errors.